 \section{Ejercicio 2}
\subsection{Introducci'on}
\setlength{\parindent}{2em}

En este ejercicio, el se'nor Bernardo Felix Souza, se compr'o una isla con dinero lavado. Dado que la isla se inundaba con las mareas, a Bernardo se le ocurri'o poner vallas con una determinada longitud y altura para evitar que se le inunde la superficie.
Bernardo necesita saber, para continuar con sus negocios ilegales, cuanta superficie de la isla permanece seca cuando viene una determinada marea, esta superficie, asumimos, la utilizar'a para cultivo de estupefacientes.

Bernardo tiene la particularidad de construir vallas que est'an sobre la isla de forma perpendicular o paralelas entre s'i y con una distancia m'inima entre ellas de 1 metro cuadrado. Cre'imos conveniente modelar este problema con un grafo, ya que nos posibilita utilizar algoritmos conocidos permitiendonos simular una inundaci'on y, a la vez, poder determinar las superficies afectadas por la marea, logrando as'i resolver el problema planteado.

Mediante un ejemplo detallaremos como traducimos la isla y sus vallas en un grafo determinado:

\begin{figure}[H]
	\centering
		\includegraphics[width=0.4\textwidth]{./dibujitos/bernardito1.png}
	\caption{Isla de Bernardo con su vallas y Bernardo en su bote preparandose para la marea alta} 
\end{figure}

El modelo utilizado tiene la siguiente forma:

\begin{itemize}
	 \item Por cada valla colocamos nodos a sus costados unidos por un eje. Este eje posee un peso determinado por la altura de la valla.
	 \item Si la valla es vertical, unimos los nodos de la izquierda consecutivos con ejes de peso cero. Lo mismo con los nodos de la derecha.
	 \item Si la valla es horizontal, unimos los nodos de arriba consecutivos con ejes de peso cero. Lo mismo con los nodos de abajo.
\end{itemize}


\begin{figure}[H]
	\centering
		\includegraphics[width=0.35\textwidth]{./dibujitos/representacionGrafo.png}
	\caption{Representaci'on incompleta de la isla mediante un Grafo. Las aristas no marcadas tienen peso cero.} 
\end{figure}	 

\newpage

Con este modelo tenemos un Grafo que rodea a las vallas, pero no tenemos forma de contar la cantidad de casilleros que quedan dentro de las mismas. Vimos que creando un rect'angulo que contenga al modelo anterior y agregando los nodos faltantes, con las respectivas aristas con peso $0$, nos permite recorrer el grafo como si fuesemos la marea, expandiendonos por los ejes siempre y cuando el peso sea menor a la marea. De esta forma podemos informarle a Bernardo que superficie de su isla se salva, acorde a la diferencia entre la superficie del rect'angulo y la cantidad de nodos que terminan inundandose.

\begin{figure}[H]
	\centering
		\includegraphics[width=0.35\textwidth]{./dibujitos/representacionGrafoCompleta.png}
	\caption{Representaci'on del rect'angulo que contiene al modelo anterior. Las aristas no marcadas tienen peso cero.} 
\end{figure}	 



\subsection{Soluci'on}

Dado nuestro modelo sobre la isla mediante un grafo con: 

\begin{itemize}
  \item nodos a los costados de las vallas

  \item aristas con peso entre ellos que significan la altura de las vallas
\end{itemize}

Se nos ocurri'o recorrer este grafo con una modificaci'on del algoritmo BFS, el cual simular'ia una inundaci'on sobre la isla.

Para buscar el rect'angulo que contenga a las vallas y por ende a la isla, decidimos buscar las coordenadas ($x$,$y$) y ($x'$,$y'$) las cuales son el extremo inferior izquierdo y el extremo superior derecho del grafo incompleto. De esta forma, conseguimos encontrar el largo y el ancho del rect'angulo que necesitamos para poder construir el grafo $G$. 

El algoritmo hace lo siguiente: dado $G$ y un nodo inicial $v$, recorre a partir de $v$, utilizando la t'ecnica de BFS, todos los vecinos de los nodos, inundandolos, mientras el peso de las aristas sea menor a la marea y los nodos no esten previamente inundados.

Si bien esta idea funciona en la mayor'ia de los casos, vimos que podiamos tener un grafo cuyas vallas esten en el borde del rect'angulo y tenga una 'unica forma de inundar la isla. Puede pasar que si elegimos mal nuestro nodo inicial, nunca inundemos la isla cuando es posible si haciesemos bien la elecci'on de $v$. Para salvar estos casos decidimos expandir los lados del rect'angulo en uno. As'i podemos arrancar a inundar desde cualquier nodo, sin preocuparnos de cual es el nodo inicial evitando este tipo de inconvenientes.

\begin{figure}[H]
	\centering
		\includegraphics[width=0.5\textwidth]{./dibujitos/representacionGrafoCompletaExpandida2.png}
	\caption{Negro Solido: Vallas. Rojo: El grafo dibujado por las paredes.
		 Verde: Nodos y Aristas de relleno.} 
	 \label{fig:representacionGrafoCompletaExpandida2}
\end{figure}

Por ejemplo, en la Figura~\ref{fig:representacionGrafoCompletaExpandida2} podemos ver que solo existe una forma de inundar la isla. 

\newpage
 
\subsection{Pseudoc'odigo}

\newcommand{\operacionSalvatajeDeDroga}{\ensuremath{\mbox{\sc operacionSalvatajeDeDroga}}}
	\begin{algorithm}[H]
		\caption{$\operacionSalvatajeDeDroga()$}\label{alg:operacionSalvatajeDeDroga}
			\medskip
			\begin{algorithmic}[1]
			\STATE contInundaciones $\leftarrow$ 0
			\STATE (base,altura) $\leftarrow$ buscarMaxMin(listaValla) 
			\STATE Grafo G $\leftarrow$  crearNodos(base,altura)
			\STATE G $\leftarrow$ crearAristas(listaValla)
			\STATE floodFill(0, 0, G)
			\STATE devolver (base * altura) - contInundaciones
			\end{algorithmic}
	\end{algorithm}

\newcommand{\floodFill}{\ensuremath{\mbox{\sc floodFill}}}
	\begin{algorithm}[H]
		\caption{$\floodFill(int x, int y, Grafo G)$}\label{alg:floodFill}
			\medskip
			\begin{algorithmic}[1]
				\STATE cola $<$nodo$>$ colaDire $\leftarrow$ $\emptyset$
				\STATE encolar(colaDire, nodo(x,y))
				\WHILE {(colaDire $\neq$ $\emptyset$)} 
				\STATE nodoActual $\leftarrow$ desencolar(colaDire)
					\FOR{(vecinos no inundados(nodoActual))}
					\IF {(nodoActual dentro de los limites y peso(eje(nodoActual,vecino)) $<$ marea)}
						\STATE encolar(colaDire, vecino)
						\STATE inundar(nodoActual)
						\STATE contInundaciones $\leftarrow$ contInundaciones + 1
					\ENDIF
					\ENDFOR
				\ENDWHILE	
			\end{algorithmic}
	\end{algorithm}

\subsubsection{Explicaci\'on del pseudoc'odigo}

Al comienzo del algoritmo inicializamos las variables globales \textbf{contInundaciones, base y altura} en 0

El algoritmo llama a las siguientes funciones:

\begin{itemize}

  \item \textbf{buscarMaxMin(listaValla)}: recorre las vallas y busca el m'aximo y m'inimo valor que determina la superficie(los nodos). Luego actualiza las variables altura y base.
  
  \item \textbf{crearNodos(base,altura)}: usando la base y la altura creamos un grafo cuya cantidad de nodos es igual a (base + 2) * (altura + 2), se expanden en 2, para evitar los casos como los de la Figura~\ref{fig:representacionGrafoCompletaExpandida2}.
  
  \item \textbf{crearAristas(listaValla)}: crea las aristas entre los nodos con peso representando la altura de las vallas.
  
  \item \textbf{floodFill(0, 0, G)}: realiza un recorrido del grafo G utilizando la t'ecnica de \textbf{BFS}. Durante el recorrido si puede inundar 	un nodo lo marca como inundado y actualiza el valor de \textit{contInundaciones}. Luego continua tratando de inundar sus vecinos. Los $0$ pasados como parametro, marcan el nodo inicial $v$.
\end{itemize}

Finalmente el algoritmo devuelve la superficie total (base * altura) menos la superficie inundada (contInundaciones).

\newpage

\subsection{Complejidad}


Analizamos la complejidad de acuerdo a las funciones que llama el algoritmo. Llamamos \textit{S} al rectangulo que contiene el grafo \textit{G}

\begin{itemize}

  \item \textbf{buscarMaxMin(listaValla)}: recorre todas las vallas buscando los m'aximos y m'inimos. Entonces la complejidad es \textit{$\theta$(longitud(listaValla))}. Como m'aximo podemos tener un rect'angulo con $base$ por $altura$ con vallas de uno de largo. Entonces \textit{$\theta$(longitud(listaValla))} $\leq$ \textit{O(\textit{S})}

  \item \textbf{crearNodos(base, altura)}: crea una matriz de nodos que representa al grafo, con las siguientes dimensiones (base + 2) * (altura + 2) e inicializamos todos los pesos de las aristas en 0. La complejidad es en todos los casos \textit{$\theta$((base + 2) * (altura + 2))} $\Rightarrow$ La complejidad nos da \textit{$\theta$(\textit{S})}.
  
  \item \textbf{crearAristas(listaValla)}: recorremos todas las vallas. Por cada valla actualizamos las aristas que las atraviezan. Como las vallas no se superponen las aristas del grafo son recorridas s'olo una vez. Entonces la funci'on recorre las aristas del grafo una 'unica vez. La complejidad es \textit{O(m)} con $m$ el total de aristas del grafo. Como $m$ es $\leq$ (base + 2) x (altura + 2) x 2 por la forma en que construimos el grafo, obtenemos una complejidad de: \textit{O(\textit{S})}.
 

  \item \textbf{floodFill(0, 0, G)}: recorre todos los nodos que pueden inundarse. En el peor caso, la marea es m'as alta que el peso de todas las aristas, recorre todos los nodos. Entonces la complejidad es O(n), siendo n la cantidad de nodos existentes en el grafo, lo que es equivalente a \textit{O((base + 2) * (altura + 2))} $\Rightarrow$ \textit{$\theta$(\textit{S})}.

\end{itemize}

Entonces la complejidad total es:

\textit{$\theta$(\textit{S})} + \textit{O(\textit{S})} + \textit{O(\textit{S})} + \textit{$\theta$(\textit{S})} $\Rightarrow$ \fbox{\textit{O(\textit{S})}}.

\subsection{Gr\'aficos}

Vamos a estudiar el comportamiento del algoritmo contando las cantidades de operaciones por cada instancia. Esperamos ver una curva lineal de acorde a la complejidad calculada (O($S$)).\\
\\
Nuestro primer caso a analizar son varias instancias de la isla poniendo una 'unica valla de largo $1$ en la coordenada ($0$,$0$) y otra del mismo largo en la coordenada ($x$,$y$) con $1 \geq x , y \geq 5000$. Esperamos encontrar en esta instancias una linea bien marcada, ya que el algoritmo recorre todo el grafo para inundar todo el recuadro que contiene a la isla, ya que las posiciones y largos de las $2$ 'unicas vallas no encierran a ninguna superficie. 

\begin{figure}[H]
	\centering
		\includegraphics[width=0.6\textwidth]{./graficos/ej2/peoresCasos.png}
	\caption{Peores Casos.} 
\end{figure}	 

En este caso encontramos el comportamiento esperado, una linea recta de acorde a la complejidad calculada teoricamente.\\
\\
Nuestro segundo caso a analizar son instancias de la isla, la cual tienen vallas cortas las cuales son colocadas al azar, incrementando el tama'no del rect'angulo que contiene la isla de forma lineal. Esperamos ver en este gr'afico peque'nos desvios con respecto a nuestro peor caso (toda la isla inundada), ya que las vallas al ser cortas y puestas de forma aleatoria aislan peque'nos espacios.

\begin{figure}[H]
	\centering
		\includegraphics[width=0.7\textwidth]{./graficos/ej2/azar.png}
	\caption{Casos al azar poco poblados.} 
\end{figure}	 

Como vemos el desv'io, con respecto al peor caso, es bastante acotado, por lo que concluimos que los islotes que se salvan en cada una de las instancias son reducidos con respecto al tama'no de la entrada.\\
\\
Nuestro tercera prueba son instancias de la isla creada de la misma forma que la anterior pero con longitudes $10$ veces mas largas. Esperamos ver un comportamiento similar, pero con desv'ios mas pronunciados.

\begin{figure}[H]
	\centering
		\includegraphics[width=0.7\textwidth]{./graficos/ej2/azarPoblados.png}
	\caption{Casos al azar poblados.} 
\end{figure}	 

% Comprobamos mediante esta instancia que los desv'ios son m'as pronunciados.\\
% \\
% Nuestro cuarto caso, es el de una isla que est'a completamente cubierta de vallas, asi cuando intentemos inundar al rect'angulo, toda la isla se ver'a a salvo del agua. Este tipo de instancias se convierten en nuestras mejores casos y esperamos ver como comparado con nuestros peores casos, y con los casos al azar, estas instancias acotan por debajo a las dem'as. 
% 
% 
% \begin{figure}[H]
% 	\centering
% 		\includegraphics[width=0.7\textwidth]{./graficos/ej2/peoresCasos.png}
% 	\caption{Mejores Casos.} 
% \end{figure}	 
% 
% Vemos como queda acotan por arriba las instancias de los peores casos y por debajo los mejores casos.
%  
\subsection{Conclusi\'on}

En este ejercicio, resolvimos el problema del se'nor Bernardo Felix Souza model'andolo con un grafo y recorri'endolo de una forma adecuada. Como vemos, si resolvemos problemas para exc'entricos millonarios nos llenar'iamos de dinero. Sin embargo concluimos que modificando levemente un algoritmo conocido como BFS pudimos encontrar de forma simple y elegante una soluci'on al problema.